#pragma once 
#include <iostream>
#include <assert.h>
using namespace std;
namespace _3s
{
  template<class K,class V>
  struct AVLTreeNode
  {
    AVLTreeNode* _left;
    AVLTreeNode* _right;
    AVLTreeNode* _parent;
    std::pair<K,V> _KV;
    int bf;
    AVLTreeNode(const std::pair<K,V> kv)
      :_left(nullptr)
      ,_right(nullptr)
      ,_parent(nullptr)
      , _KV(kv)
      ,bf(0)
    {}
  };
 //节点 
  template<class K,class V>
  class AVLTree
  {
    typedef AVLTreeNode<K,V> Node;
    public:
    //插入
    bool insert(const std::pair<K,V>& kv)
    {
      if(root==nullptr)
      {
        root=new Node(kv);
        return true;
      }
      Node* parent=nullptr;
      Node* cur=root;
      while(cur)
      {
          if(cur->_left.first<kv.first)
          {
            parent=cur;
            cur=cur->_right;
          }
          else if(cur->_left.first>kv.first)
          {
            parent=cur;
            cur=cur->_left;
          }
          else 
          {
            return false;
          }      
     }
      cur=new Node(kv);
      if(parent->_kv.first>kv.first)
      {
        parent->left=cur;
        parent->bf--;
      }
      else 
      {
        parent->right=cur;
        parent->bf++;
      }
      cur->_parent=parent;
      while(parent)
      {

      
      if(abs(parent->bf)==1)
      {
         parent=parent->_parent;
         cur=cur->_parent;
        
      }
      else if(abs(parent->bf)==2)
      {
        if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if ((parent->_bf == -2 && cur->_bf == -1))
				{
					RotateR(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}

				break;

      }
      else 
      {
        assert(false);
      }
     }
      return true;
    }
    private:
    	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* ppNode = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;

		if (root == parent)
		{
			root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}

			subR->_parent = ppNode;
		}

		subR->_bf = parent->_bf = 0;
	}

   private:
     Node* root=nullptr;
  };
}
